{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Groups Entering a Competition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分组的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>grades</code> ，表示大学中一些学生的成绩。你打算将 <strong>所有</strong> 学生分为一些 <strong>有序</strong> 的非空分组，其中分组间的顺序满足以下全部条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第 <code>i</code> 个分组中的学生总成绩 <strong>小于</strong> 第 <code>(i + 1)</code> 个分组中的学生总成绩，对所有组均成立（除了最后一组）。</li>\n",
    "\t<li>第 <code>i</code> 个分组中的学生总数 <strong>小于</strong> 第 <code>(i + 1)</code> 个分组中的学生总数，对所有组均成立（除了最后一组）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可以形成的 <strong>最大</strong> 组数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grades = [10,6,12,7,3,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>下面是形成 3 个分组的一种可行方法：\n",
    "- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1\n",
    "- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2\n",
    "- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 \n",
    "可以证明无法形成超过 3 个分组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grades = [8,8]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grades.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grades[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-groups-entering-a-competition](https://leetcode.cn/problems/maximum-number-of-groups-entering-a-competition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-groups-entering-a-competition](https://leetcode.cn/problems/maximum-number-of-groups-entering-a-competition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,6,12,7,3,5]', '[8,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        if n < 3:\n",
    "            return 1\n",
    "        else:\n",
    "            group = 0\n",
    "            m = n\n",
    "            i = 1\n",
    "            while m >= i:\n",
    "                m -= i\n",
    "                i += 1\n",
    "                group += 1\n",
    "        return group\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return floor((sqrt(1 + 8 * len(grades)) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n=len(grades)\n",
    "        ans=0\n",
    "        num=0\n",
    "        for i in range(1,n+2):\n",
    "            num+=1\n",
    "            ans+=i\n",
    "            if ans>n:\n",
    "                return num-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "\n",
    "        l = len(grades)\n",
    "\n",
    "        return floor((sqrt(1+8*l)-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        l, r = 1, n + 10\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if mid * (mid + 1) // 2 <= n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n= len(grades)\n",
    "        return int(math.sqrt(2.0 * n + 0.25) - 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        # 1 + 2 + 3 + 4 + 5 == n\n",
    "        #\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if mid * (mid + 1) <= 2 * n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = int(math.sqrt(len(grades)*2))\n",
    "        return n-1 if n*(n+1)//2 > len(grades) else n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        grades.sort()\n",
    "        n=len(grades)\n",
    "        i=x=1\n",
    "        while i<=n:\n",
    "            x+=1\n",
    "            i=x*(x+1)//2\n",
    "        return x-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "\n",
    "        n = len(grades)\n",
    "        l, r = 1, n + 10\n",
    "        while l<r:\n",
    "            mid = l + r >> 1\n",
    "            if mid * (mid + 1) // 2 <= n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        ans = 0\n",
    "        t = 1\n",
    "        c = 0\n",
    "        for _ in range(n):\n",
    "            c += 1\n",
    "            if c == t:\n",
    "                ans += 1\n",
    "                t += 1\n",
    "                c = 0\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        grades.sort()\n",
    "        groupCnt = 1\n",
    "        preGroupMax = 0\n",
    "        curCnt = 0\n",
    "        ans = 0\n",
    "        for i in range(len(grades)):\n",
    "            curCnt += 1\n",
    "\n",
    "            if curCnt == groupCnt:\n",
    "                groupCnt += 1\n",
    "                curCnt = 0\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        x = 0\n",
    "        while x * (x + 1) // 2 <= n:\n",
    "            x += 1\n",
    "        return x - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1 + 8 * len(grades)) - 1) * 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n=len(grades)\n",
    "        t=1\n",
    "        while t*(t+1)//2<=n:\n",
    "            t+=1\n",
    "        return t-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        left, right = 0, n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * (mid + 1) <= 2 * n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        if len(grades) == 1:\n",
    "            return grades[0]\n",
    "        n = len(grades)\n",
    "        l, r = 1, n \n",
    "        while l<r:\n",
    "            mid = l + r >> 1\n",
    "            if mid * (mid + 1) // 2 <= n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        size = len(grades) * 2\n",
    "        i = 1\n",
    "        while i <= (size) // (i + 1):\n",
    "            i += 1\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((-1 + math.sqrt(1 + 8 * len(grades))) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = int(math.sqrt(len(grades)*2))\n",
    "        if n*(n+1)//2 > len(grades):\n",
    "            n = n-1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        if len(grades)==2:\n",
    "            return 1\n",
    "        s,i = 0,0\n",
    "        while s<len(grades):\n",
    "            s+=i\n",
    "            i+=1\n",
    "            if s>len(grades):\n",
    "                i-=1\n",
    "        return i-1\n",
    "            \n",
    "           \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        mx = 1\n",
    "        l = 1\n",
    "        n = len(grades)\n",
    "        while mx <= n:\n",
    "            l += 1\n",
    "            mx += l\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        return int((sqrt(8*n+1)-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        grades.sort()\n",
    "        groupCnt = 1\n",
    "        preGroupMax = 0\n",
    "        curCnt = 0\n",
    "        ans = 0\n",
    "        for i in range(len(grades)):\n",
    "            if grades[i] > preGroupMax:\n",
    "                curCnt += 1\n",
    "            else:\n",
    "                groupCnt += 1\n",
    "\n",
    "            if curCnt == groupCnt:\n",
    "                groupCnt += 1\n",
    "                curCnt = 0\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1 + 8 * len(grades)) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        grades.sort()\n",
    "        ans = 1\n",
    "        pre = grades[0]\n",
    "        pre_cnt = 1\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            s = 0\n",
    "            cnt = 0\n",
    "            while i < n and not (s > pre and cnt > pre_cnt):\n",
    "                s += grades[i]\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            if s > pre and cnt > pre_cnt:\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans\n",
    "            pre = s \n",
    "            pre_cnt = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return floor((sqrt(1 + 8 * len(grades)) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n  = len(grades)\n",
    "        return int((sqrt(8 * n + 1) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1+8*len(grades))-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        result = int(math.sqrt(len(grades) * 2))\n",
    "        if result * (result + 1) > 2 * len(grades):\n",
    "            result = result - 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1+8*len(grades))-1)/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        length = len(grades) * 2\n",
    "        temp = int(math.sqrt(length))\n",
    "        if length >= temp * (temp + 1):\n",
    "            return temp\n",
    "        else:\n",
    "            return temp - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        ans, l, r = 0, 1, n\n",
    "        grades.sort()\n",
    "\n",
    "        def check(target: int):\n",
    "            cnt, i, p, q, t, s = 0, 0, 0, 0, 0, 0\n",
    "            while i < n:\n",
    "                p += grades[i]\n",
    "                q += 1\n",
    "                i += 1\n",
    "                if p > s and q > t:\n",
    "                    cnt += 1\n",
    "                    t, s, p, q = q, p, 0, 0\n",
    "            return cnt >= target\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        pre = 1\n",
    "        n -= 1\n",
    "        while n > pre:\n",
    "            pre += 1\n",
    "            n -= pre \n",
    "        return pre "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, g: List[int]) -> int:\n",
    "        n=len(g)\n",
    "        curLen=1\n",
    "        cnt=0\n",
    "        while n>=curLen:\n",
    "            cnt+=1\n",
    "            n-=curLen\n",
    "            curLen+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        ret = 1\n",
    "        while ret * (ret + 1) // 2 <= n:\n",
    "            ret += 1\n",
    "        return ret - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        n = len(grades)\n",
    "        pre = 1\n",
    "        n -= 1\n",
    "        while n > pre:\n",
    "            pre += 1\n",
    "            n -= pre \n",
    "        return pre "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        grades.sort()\n",
    "        n = len(grades)\n",
    "        l, r = 1, n + 10\n",
    "        while l<r:\n",
    "            mid = l + r >> 1\n",
    "            if mid * (mid + 1) // 2 <= n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1 + 8 * len(grades)) - 1) * 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGroups(self, grades: List[int]) -> int:\n",
    "        return int((sqrt(1 + 8 * len(grades)) - 1) * 0.5)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
